1. Field of the Invention
The present invention concerns a method of inserting an additional information item such as a watermark in a digital signal.
It also concerns a method of authenticating a digital signal from a watermark inserted in the signal.
Correlatively, the present invention concerns a device for inserting an additional information item and a device for authenticating a digital signal adapted respectively to implement the insertion and authentication methods according to the invention.
2. Description of Related Art
The present invention concerns in general terms the authentication of digital data, and more particularly digital images. Its purpose is to allow the detection of changes occurring in original digital data.
More precisely, the authentication method according to the invention comes within the technical field of watermarking of digital data which can be interpreted as the insertion of a seal in the digital data, enabling the content of an original digital data file to be authenticated.
In a conventional fashion, and as described for example in the European patent application EP 0 766 468 filed in the name of NEC CORPORATION, watermarking techniques can be used for protecting copyright over a digital document. In such a case, the watermark inserted must, amongst other things, be robust to the different manipulations performed on the digital data, and notably the conventional techniques of digital data compression.
Unlike the digital data watermarking techniques aimed at protecting the author of a digital document, watermarking techniques for authenticating the data themselves must make it possible to detect any change to or manipulation of the digital data. The watermark inserted for authenticating original digital data must consequently not be robust to the various conventional manipulations of the image.
In addition to its fragility with regard to the changes undergone by the document, this inserted watermark must be imperceptible, for the purpose of preserving the quality of the digital document, and notably the visual quality when the document to be authenticated is a digital image, and be difficult to counterfeit in order to prevent a counterfeiter from reinserting the same watermark in digital data which have been modified.
Such a method of authenticating digital data by the insertion of a watermark in the data is described in the article entitled xe2x80x9cDigital watermarking using multiresolution wavelet decompositionxe2x80x9d by D KUNDUR and D HATZINAKOS, Proc. ICASSP, pages 2969-2972, May 1998.
This method thus makes it possible to insert an additional information item, which can for example contain information on the origin of the data or their date of creation, and to sign these original data.
However, in this article, the insertion and authentication method described requires the spectral wavelet decomposition of a digital image to be authenticated and then the reverse wavelet spectral recomposition of the digital image after insertion of the watermark.
In addition to the fact that this spectral decomposition is expensive in calculation time, the method described makes it possible to authenticate only an original digital image but does not make it possible to protect digital data already compressed by various coding methods.
The aim of the present invention is notably to propose a method of inserting an additional information item with a view to the authentication of digital data which make it possible to detect digital data in various spectral or spatial representation fields.
It makes it possible notably to insert an additional information item in digital data which are compressed in order to be stored or transmitted, in a manner compatible with the compression used.
The insertion method is applied to a digital signal decomposed into a set of coefficients, each coefficient being represented in L bits, and makes it possible to insert an additional information item represented by a set of binary values with the same size as the set of coefficients representing the digital signal to be authenticated.
The method comprises calculating, for at least one coefficient, a check bit, and then substituting a coefficient watermarked as a function of the check bit and a binary value of the additional information item for the said at least one coefficient.
According to the invention, the insertion method is characterised in that it includes the following steps:
calculating, for at least one coefficient, a check bit in accordance with a predetermined operation as a function of L-M first bit planes of said coefficient;
calculating M last bit planes according to a predetermined rule which is reversible as a function of the check bit and a binary value of the additional information item; and
substituting the M last bit planes calculated for the M last bit planes of said coefficient.
Thus the method of inserting a watermark according to the invention is applied to any digital signal provided that it is represented by a set of spatial or spectral coefficients.
The insertion method can thus be applied notably directly to a compressed representation of a digital signal.
The additional information is incorporated directly in the digital signal, by modifying only the last bit planes of the coefficients, that is to say the least significant bits LSB of the coefficients so that it remains imperceptible.
In addition, the check bit calculated from the coefficient itself depends only on the first bit planes, that is to say the most significant bit planes of the coefficient. These first L-M bit planes are not modified during the substitution step, which has the advantage, during the authentication of the digital signal, of being able to recalculate, for each coefficient, a check bit identical to that calculated at the time of insertion of the additional information and to facilitate the detection of any changes made to the original digital signal.
According to a symmetrical aspect of the invention, a method of authenticating a digital signal, from an additional information item, such as a watermark, inserted in the digital signal by the insertion method as described above, is characterised in that it includes the following steps:
calculating, for at least one coefficient, a check bit according to said predetermined operation as a function of L-M first bit planes of said coefficient;
extracting the value of the additional information item inserted in accordance with said predetermined rule which is reversible as a function of the check bit and the last M bit planes;
comparing the extracted value of the additional information item inserted and the binary value of the additional information item; and
deciding whether or not to authenticate the digital signal depending on whether or not said extracted value and said binary value of the inserted additional information item are identical.
As described previously, the authentication method is all the more simple to implement since the check bit, calculated from unmodified bit planes of the coefficients, is identical to that calculated during the calculation step of the insertion method.
It is thus possible, at the extraction step, to use a deterministic rule which is simple to reverse in order to extract the binary value of the additional information item inserted.
In addition, according to the spectral or spatial representation of the digital signal by the coefficients, the authentication method makes it possible to locate, in the representation space, the changes made to the digital signal.
Moreover, as before, the authentication method makes it possible to authenticate a compressed representation of a digital signal and is therefore intrinsically robust with respect to the compression algorithm used.
According to a preferred characteristic of the invention, at the step of calculating a check bit of the insertion method and authentication method, said predetermined operation is a function of the L-M first bit planes and a confidential key represented in L bits.
Although optional, the use of a confidential key makes the insertion of the additional information item in the digital signal more certain and more difficult to counterfeit.
Advantageously, said predetermined operation consists of effecting a sum of binary operations on the first L-M bit planes of the said coefficient and the first L-M bit planes of the said confidential key and calculating the check bit as a function of the parity of the said sum.
The step of calculating a check bit is thus implemented simply and rapidly on the coefficients representing the digital signal.
According to a preferred characteristic of the invention, which makes it possible to make the inserted additional information item imperceptible as far as possible, the number M of substituted bit planes is equal to 1 or 2.
According to another preferred characteristic of the invention, at the step of calculating the last M bit planes of the insertion method, the value of the last bit plane is equal to the value of the check bit or to the alternative value of the check bit depending on the state of the binary value of the additional information item.
Correlatively, at the extraction step of the authentication method, the value of the additional information is equal to one state or another state depending on whether or not the value of the last bit plane is equal to the value of the check bit.
The calculation rule used at the time of insertion is particularly simple to implement using the value of the check bit and the value of the additional information item to be inserted.
It also has the advantage of being simple to reverse for authenticating the digital signal in order to find, from the value of the check bit and the value of the last bit plane, the binary value of the information which is assumed to have been inserted.
According to an advantageous characteristic of the insertion method, the number of substituted bit planes is equal to 2 and, at the step of calculating the last M bit planes, the value of the penultimate bit plane is equal to the alternative value of the last bit plane.
Correlatively, at the extraction step of the authentication method, the number of bit planes is equal to 2 and the value of the additional information item is extracted only if the value of the penultimate bit plane is equal to the alternative value of the last bit plane.
This characteristic is an advantage at the time of authentication of the digital signal since the probability of a modified coefficient nevertheless making it possible to extract a correct value of the inserted information is lower since the last two bit planes must have been modified whilst keeping alternate values.
According to a preferred embodiment of the invention, when the digital signal is decomposed into a set of quantized spectral coefficients, the insertion method also includes a prior step of choosing a subset of quantized spectral coefficients, in which the chosen coefficients have at least a magnitude strictly greater than zero, the steps of calculating a check bit, calculating the last M bit planes and substituting being implemented for each coefficient of said subset.
Restricting the coefficients able to be modified to a subset of non-nil coefficients avoids modifying the coefficients set to zero at the time of quantization of the digital signal. In this way the advantages of quantization of the digital signal in order to compress it are not lost.
Advantageously, the subset of coefficients includes the quantized spectral coefficients whose magnitude is greater than a threshold value.
The threshold value can thus be fixed so that the coefficients liable to be modified have a sufficiently high magnitude for the substitution of the last bit planes to be of little significance with respect to the value of the coefficient.
In this preferred embodiment of the invention, the set of binary values representing the additional information item is advantageously generated by the repetition of an initial binary information item with a size smaller than the size of the set of quantized spectral coefficients.
This provision makes it possible to increase the probability of all the initial binary information being inserted in the digital signal even if certain coefficients are not liable to be modified.
On the other hand, if the additional information item has an identical resolution to that of the digital signal to be authenticated, certain binary values are not inserted when they correspond to quantized spectral coefficients with a magnitude less than the predetermined threshold value.
Correlatively, the authentication method, in this preferred embodiment, also includes a prior step of choosing a subset of quantized spectral coefficients, in which the chosen coefficients have a magnitude greater than a threshold value, the steps of calculating a check bit, extracting, comparing and deciding being implemented for each coefficient of the said subset.
This characteristic makes it possible to implement the authentication method only on all the coefficients liable to have been modified during the insertion of the additional information item.
According to an advantageous characteristic of the invention, which affords a practical implementation of the present invention for authenticating a digital signal stored in a compressed file, the insertion method also includes a prior step of entropic decoding adapted to extract the quantized spectral coefficients and a step of entropic coding after said substitution step.
Likewise, the authentication method for authenticating a digital signal stored in a compressed file also includes a prior step of entropic decoding adapted to extract the quantized spectral coefficients.
Correlatively, the present invention also concerns a device for inserting an additional information item such as a watermark for authenticating a digital signal decomposed into a set of coefficients, each coefficient being represented in L bits, and said additional information item being represented by a set of binary values of the same size as said set of coefficients, characterised in that it has:
means of calculating a check bit in accordance with a predetermined operation as a function of L-M first bit planes of a coefficient;
means of calculating M last bit planes according to a predetermined rule which is reversible as a function of the check bit and a binary value of the additional information item; and
means of substituting the last M bit planes calculated for the last M bit planes of said coefficient.
Likewise, the present invention concerns a device for authenticating a digital signal from an additional information item such as a watermark inserted in said digital signal by the insertion method according to the invention, said digital signal being decomposed into a set of coefficients, each coefficient being represented in L bits, characterised in that it has:
means of calculating a check bit according to said predetermined operation as a function of L-M first bit planes of a coefficient;
means of extracting the value of the additional information item inserted in accordance with said predetermined rule which is reversible as a function of the check bit and the last M bit planes of said coefficient;
means of comparing the extracted value of the additional information item inserted and the binary value of the additional information item; and
means of deciding whether or not to authenticate the digital signal according to whether or not said extracted value and said binary value of the inserted additional information item are identical.
These insertion and authentication devices have preferential characteristics and advantages similar to those described previously for the insertion method and the authentication method.
In one particular embodiment of the invention, the latter further permits authentication of a compressed signal, with a tolerance in relation to a slight over-compression of the signal. An signal over-compressed within an adjustable limit can be authenticated as being a correct signal.
For this purpose, the invention provides a method of inserting an additional information item such as a watermark for authenticating a digital signal comprising a set of coefficients, the said additional information item being represented by a set of binary values with a size smaller than that of the said set of coefficients, characterised in that it includes the steps of:
determining a set of parameters representing the signal, with a size at least equal to that of the set of binary values
quantizing the parameters representing the signal according to a predetermined quantization pitch;
inserting the binary values in the quantized representative parameters;
dequantizing the parameters previously processed;
inserting the dequantized parameters in the signal.
Correlatively, the invention relates to a device for inserting an additional information item such as a watermark for authenticating a digital signal comprising a set of coefficients, the said additional information item being represented by a set of binary values with a size smaller than that of the said set of coefficients, characterised in that it includes:
means of determining a set of parameters representing the signal, with a size at least equal to that of the set of binary values;
means of quantizing the parameters representing the signal according to a predetermined quantization pitch;
means of inserting the binary values in the quantized representative parameters;
means of dequantizing the parameters previously processed;
means of inserting the dequantized parameters in the signal.
Thanks to the above characteristics, a signal that may possibly have been over-compressed, within an adjustable limit, can be authenticated.
The choice of quantization pitch makes it possible to adjust the compromise between over-compression tolerance and the quality of the watermarked signal.
According to one preferred characteristic, the binary values are inserted in the quantized representative parameters according to the method initially presented, in which the set of coefficients in question is the set of quantized representative parameters.
According to preferred characteristics and alternatives, the set of the representative parameters comprises mean values of the coefficients calculated for blocks of coefficients of the signal, or the set of representative parameters comprises low-frequency coefficients of a frequency decomposition carried out in blocks.
The first case applies when the signal to be processed is represented in raw data, whereas the second applies to the case in which the signal is in a compressed form involving frequency decomposition.
The insertion device according to the invention comprises means for implementing the above characteristics.
The invention also relates to a method of authenticating a digital signal from an additional information item such as a watermark inserted in the said digital signal by the insertion method presented above, the said additional information item being represented by a set of binary values with a size smaller than that of the said set of coefficients, characterised in that it includes the steps of:
determining a set of parameters representing the signal, with a size at least equal to that of the set of binary values;
quantizing the parameters representing the signal according to a predetermined quantization pitch;
extracting additional information values from the said quantized representative parameters;
comparing the values extracted with the values of the additional information item;
deciding whether or not to authenticate the digital signal as a function of the result of the comparison step.
Correlatively, the invention relates to a device for authenticating a digital signal from an additional information item such as a watermark inserted in the said digital signal by the insertion device presented above, the said additional information item being represented by a set of binary values with a size smaller than that of the said set of coefficients, characterised in that it includes:
means of determining a set of parameters representing the signal, with a size at least equal to that of the set of binary values;
means of quantizing the parameters representing the signal according to a predetermined quantization pitch;
means of extracting additional information values from the said quantized representative parameters;
means of comparing the values extracted with the values of the additional information item;
means of deciding whether or not to authenticate the digital signal as a function of the result supplied by the comparing means.
The present invention also concerns a computer, a digital signal processing apparatus, a digital photographic apparatus or a digital camera having means adapted to implement the insertion method and/or means adapted to implement the authentication method.
It also concerns a computer, a digital signal processing apparatus, a digital photographic apparatus or a digital camera comprising an insertion device and/or an authentication device according to the invention.
The present invention also relates to an information storage means which can be read by a computer or by a microprocessor, integrated or not into an insertion or authentication device, possibly removable, which stores a program implementing the insertion or authentication method according to the invention.
The characteristics and advantages of this computer, digital signal processing apparatus, digital photographic apparatus, digital camera or storage means are identical to those disclosed above.
Other particularities and advantages of the invention will also emerge from the following description.